package com.jxm.tree;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * @Author: jxm
 * @Description: 并查集 案例-畅通工程
 * @Date: 2022/7/29 16:35
 * @Version: 1.0
 */
public class Traffic_Project {

    public static void main(String[] args)throws Exception {
        //创建输入流
        BufferedReader reader = new BufferedReader(new
                InputStreamReader(Traffic_Project.class.getClassLoader().getResourceAsStream("traffic_project.txt")));
        //读取城市数目，初始化并查集
        int number = Integer.parseInt(reader.readLine());
        UF_Tree_Weighted uf = new UF_Tree_Weighted(number);
        //读取已经修建好的道路数目
        int roadNumber = Integer.parseInt(reader.readLine());
        //循环读取已经修建好的道路，并调用union方法
        for (int i = 0; i < roadNumber; i++) {
            String line = reader.readLine();
            int p = Integer.parseInt(line.split(" ")[0]);
            int q = Integer.parseInt(line.split(" ")[1]);
            uf.union(p,q);
        }
        //获取剩余的分组数量
        int groupNumber = uf.count();
        //计算出还需要修建的道路
        System.out.println("还需要修建"+(groupNumber-1)+"道路，城市才能相通");
    }
}
